class Solution
{
public:
    int maximumSafenessFactor(vector<vector<int>> &grid)
    {
        int n = grid.size();

        vector<vector<int>> safetyMap(n, vector<int>(n, 0));

        queue<pair<int, int>> q;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 1)
                {
                    q.push({i, j});
                }
            }
        }

        int safety = 0;
        while (!q.empty())
        {
            int qSize = q.size();
            for (int i = 0; i < qSize; ++i)
            {
                auto [x, y] = q.front();
                q.pop();
                safetyMap[x][y] = safety;
                if (x > 0 && grid[x - 1][y] == 0)
                {
                    grid[x - 1][y] = 1;
                    q.push({x - 1, y});
                }
                if (x < n - 1 && grid[x + 1][y] == 0)
                {
                    grid[x + 1][y] = 1;
                    q.push({x + 1, y});
                }
                if (y > 0 && grid[x][y - 1] == 0)
                {
                    grid[x][y - 1] = 1;
                    q.push({x, y - 1});
                }
                if (y < n - 1 && grid[x][y + 1] == 0)
                {
                    grid[x][y + 1] = 1;
                    q.push({x, y + 1});
                }
            }
            ++safety;
        }

        int result = safetyMap[0][0];
        auto compareSafety = [&](const pair<int, int> &a, const pair<int, int> &b)
        {
            return safetyMap[a.first][a.second] < safetyMap[b.first][b.second];
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compareSafety)> pq(compareSafety);
        pq.push({0, 0});
        vector<vector<int>> visited(n, vector<int>(n, 0));
        visited[0][0] = 1;
        while (!pq.empty())
        {
            auto [x, y] = pq.top();
            pq.pop();
            result = min(result, safetyMap[x][y]);

            if ((x == n - 1 && y == n - 1) || result == 0)
            {
                return result;
            }

            if (x > 0 && visited[x - 1][y] == 0)
            {
                visited[x - 1][y] = 1;
                pq.push({x - 1, y});
            }
            if (x < n - 1 && visited[x + 1][y] == 0)
            {
                visited[x + 1][y] = 1;
                pq.push({x + 1, y});
            }
            if (y > 0 && visited[x][y - 1] == 0)
            {
                visited[x][y - 1] = 1;
                pq.push({x, y - 1});
            }
            if (y < n - 1 && visited[x][y + 1] == 0)
            {
                visited[x][y + 1] = 1;
                pq.push({x, y + 1});
            }
        }
        return 0;
    }
};